In many applications, computers and processors maintain some form of real time for reference and sequencing purposes, and for the purpose of synchronization of activities with other computers or processors. In particular, in network and multiprocessing architectures, time synchronization between network nodes is important.
Generally, such devices maintain a register or other hardware or software structure which contains a representation of real time. This time representation can be either a literal time (such as Universal Time, Greenwich Mean Time, Eastern Standard Time, etc.) or some suitable form of logical time. In either case, the device maintaining the time representation updates the time internally on a real time basis. For instance, a processor might have a hardware timer which provides an interrupt at a known real time interval, measured in terms of system hardware clock cycles. Responsive to the interrupt, the processor updates its internal time in accordance with the known real time interval between interrupts.
In addition to maintaining and updating time internally, a processor or network node synchronizes its internal time with an external reference time source. A processor which has been synchronized to an external time source measures time in accordance with its internal hardware clock, which operates at a known frequency. Since the hardware clock frequency is inevitably not perfectly accurate, as time goes by the internal time maintained by a processor diverges from the external time with which the processor was previously synchronized. This time divergence is sometimes called "clock drift". Typically the processor's time drifts linearly from the external time. To prevent the clock drift from getting too large, from time to time the processor resynchronizes its internal time with the external reference time.
Various arrangements may be used for providing a reference time source. For instance, in a network comprising a plurality of nodes, one of the nodes serves as a repository of a reference time. All other nodes of the network are synchronized with that node's time.
Another time synchronization method involves reception of a reference time from a time source external to the network. Time services exist, which provide accurate time information for various purposes, including computer or network synchronization. One well known time source is WWV, which broadcasts a Universal Time signal. WWV and other similar time sources may be used to provide time synchronization to computers and processors. As described above, a processor which is synchronized with such a time source gradually drifts out of synchronization. Also, time sources such as WWV occasionally introduce "leap seconds" to synchronize their time with the motions of the planet Earth. To prevent error from accumulating due to drift and leap seconds, it is particularly desirable that a processor synchronize itself with an external time source from time to time in the normal course of its operation.
In architectures in which a predetermined node is a reference time source, or in which an external reference time source, such as a subscription time service, is coupled through a suitable communication link or interface to a predetermined node of a network, the predetermined node may be characterized as a master node.
In order for the master node to synchronize other nodes, the master node must know which other nodes it is responsible for updating, so that it can direct appropriate time update messages to those nodes. The master node sends synchronization messages to other nodes coupled to the network, which are slave nodes relative to the predetermined node. In addition, to guarantee that the slave nodes are properly updated, the master node must receive responses from each of the slave nodes. In this scenario, a handshaking scheme is employed, in which a message is sent and then an acknowledgement is awaited.
A handshaking scheme is also employed if a slave node sends a synchronization request message to the master node, and the master node responds by sending a synchronization message. The inaccuracy of time provided to a slave node in these scenarios is related to the total elapsed time for the handshaking sequence of messages. This inaccuracy is thus likely to be undesirably large, particularly if each slave receiving a synchronization message must separately acknowledge it.
A technique called Probabilistic Clock Synchronization has been used for synchronizing internal times of nodes with reference time from a designated reference node or from an external source. The technique is described in Christian, "Probabilistic Clock Synchronization", IBM Technical Disclosure Bulletin, Vol. 31, No. 2 (July 1988), p. 91. A slave node sends a synchronization request at a time t, according to its clock. A master responds with a message giving a time T, according to the master's time clock. The slave receives the response at a time t', according to its clock. It is thus established that the master's time T fails between the slave's times t and t'. The slave then updates its internal time in accordance with a difference between the reference time T and an internal time halfway between t and t'. The slave node's synchronization is accurate to within ##EQU1##
Thus, the technique described in Christian advantageously provides both synchronization and a quantitative estimation of the accuracy of synchronization, i.e., an upper bound of synchronization error. However, this technique has the drawback that the nodes must have knowledge of each other's IDs. Thus, the scheme is not well equipped to deal with nodes coming on line or going off line, or changes in network configuration, because the master node must be informed of these conditions and must integrate them into its records of the network configuration so that it will know which slave nodes it must communicate with. The scheme is also not well equipped to deal with multiple (redundant) external time sources, which are often present in large architectures including several linked networks. Additionally, the bidirectional message protocol requires a substantial amount of overhead. This is particularly true for the master node, which must go through the synchronization protocol for each slave node for which the master is responsible.
An alternative approach to network time synchronization may be used, in which the nodes maintain a peer relationship, rather than a master-slave relationship. One example of this arrangement is described in Dolev et al, "Dynamic Fault-Tolerant Clock Synchronization", IBM Research Report RJ8576 (Jan. 16, 1992). This Research Report describes systems in which, from time to time, processors in a network compare their internal times and synchronize based on an average time. Such systems can accommodate processors which fail and then recover, and processors which join the network while the network is in operation.
Additionally, the Research Report describes a method in which network processors periodically synchronize each other after an initialization. The synchronization algorithm is described in section 3 of the Report. Processors "sign" a synchronization message containing a reference time for synchronization, and send the message to each other. A message accumulates a plurality of signatures as it passes between processors. Thus this method has several drawbacks. First, it requires some overhead in maintaining knowledge of what other processors are in the network. Second, a large amount of time is consumed exchanging messages. Third, this method fails to provide an upper bound of inaccuracy of synchronization.
Another example of such a network time synchronization scheme is given in U.S. Pat. No. 5,001,730, issued to Franaszek et al, titled "Clock Synchronization Algorithm for Address Independent Networks". Each node in a network maintains an internal time, and keeps track of when a known time interval has elapsed. The node sends a synchronization message based on its internal time at one end of the interval, unless, prior to the end of the interval, it has received a synchronization message already sent from another node. Therefore, each time the known interval elapses, the nodes resynchronize. Often, after the first three or four resynchronizations, the network reaches a steady state in which one of the nodes, having the fastest internal clock, always sends the synchronization message.
In Franaszek, the precision with which each node synchronizes itself is a value given by an expression which takes into account an upper and lower bound of accuracy of the node's internal clock frequency and an upper and lower bound of a delay during which the message is transmitted from one node to another and is processed by the other node. Thus, the Franaszek arrangement has the drawback that its processing time, which might include a considerable delay due to other tasks being active at the time the synchronization message is received, increases the upper bound of inaccuracy of synchronization to produce an undesirably large value.
Yet another consideration relating to network time synchronization relates to operation in the presence of a system fault. A network node or link between nodes could fail. In addition, an external time source could fail, or a link between the external source and the network could fail. In a master/slave network, if a master node lost communication with the external source, it would no longer be able to synchronize other nodes. Also, if any node depended upon communication from or through another node for time synchronization, and that other node failed or communication with it was lost, then the first node would have no means for synchronization.
In summary, an important objective of a time synchronization scheme for network nodes is to provide a quantitative measurement of the upper bound of synchronization error for each synchronized node. This upper bound of synchronization error should be kept as small as possible, and should be achieved with the smallest practicable processing and memory overhead. Also, a time synchronization scheme should be able to accommodate multiple or redundant time sources. Finally, a method for time synchronization which achieves these objectives should also be able to function effectively in the event of a failure of a node, a link, or an external time source. Conventional master/slave oriented systems, such as probabilistic clock synchronization systems, provide estimates of synchronization error, but they require considerable overhead and bidirectional message traffic, leading to large upper bounds of synchronization error. Conventional anonymous synchronization schemes reduce overhead, but do not provide estimates of synchronization error.